package com.sali.DP;

/**
 * @author sali
 * @date 2025/6/2 16:17
 */
public class JZ_83 {

    final int MOD = 998244353;
    public long cutRope (long number) {
        // write code here
        if (number == 2) {
            return 1;
        }
        if (number == 3) {
            return 2;
        }

        if (number % 3 == 0) {
            return pow(3, number / 3);
        } else if (number % 3 == 1) {
            return 2 * 2 * pow(3, (number - 4) / 3) % MOD;
        } else {
            return (2 * pow(3, (number - 2) / 3)) % MOD;
        }
    }

    //快速幂函数:求a的n次幂
    public long pow(long a, long n) {

        long result = 1;

        while (n > 0) {
            if ((n & 1) == 1) {
                result = (result * a) % MOD;
            }
            a = (a * a) % MOD;
            n >>= 1;
        }
        return result;
    }
}
